package com.work.leecode.array.easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author huangxianjin <huangxianjin@kuaishou.com>
 * Created on 2024-04-10
 */
/*
 *合并两个有序数组---88
 */
public class Lc88 {
    public static void main(String[] args) {
        //两个非递减排序数组
        int[] nums1 = {-2, 1, 1, 3, 5, 0, 0, 0};
        int m = 5;
        int[] nums2 = {3, 4, 9};
        int n = 3;
//        merge1(nums1, m, nums2, n);
//        merge2(nums1, m, nums2, n);
//        merge3(nums1, m, nums2, n);
//        merge4(nums1, m, nums2, n);
        merge5(nums1, m, nums2, n);
    }

    //方法一： Collections.sort
    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < m + n; i++) {
            if (i < m) {
                list.add(nums1[i]);
            } else {
                list.add(nums2[i - m]);
            }
        }
        Collections.sort(list);
        System.out.println(list);
    }

    //方法二：Arrays.sort
    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
        System.out.println(Arrays.toString(nums1));
    }

    //方法三：双指针---利用已经数组已经排好序的特点
    public static void merge3(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
        System.out.println(Arrays.toString(nums1));
    }


    //2024-06-24复习
    //方法一：数组直接合并
    public static void merge4(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
        System.out.println(Arrays.toString(nums1));
    }

    //方法二：双指针
    public static void merge5(int[] nums1, int m, int[] nums2, int n) {
        //两个指针
        int p1 = 0, p2 = 0;
        //保存结果的list
        ArrayList<Integer> res = new ArrayList<>();

        //当前值
        int cur = 0;

        //循环遍历两个数组
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            res.add(cur);
        }
        for (int i = 0; i < m + n; i++) {
            nums1[i] = res.get(i);
        }
        System.out.println(Arrays.toString(nums1));
    }
}
